//C,C++预处理指令,能够保证头文件只被编译一次
#pragma once
//使用using起别名
using Rank = unsigned int;
//define 不需要等于号，不可以加分号
#define DEFAULT_CAPACITY  10

//向量模板类
template<typename T>
class Vector {
protected:
    Rank size; //规模
    Rank capacity; //容量
    T* elem; //数据区
    void copyFrom(T const *A, Rank lo, Rank hi); //复制数组区间A[lo, hi)
public:
    /**
     * 构造函数
     */
    //参数里默认值，就是缺省参数，相当于空构造器,容量为c、规模为s、所有元素初始为值v
    Vector(Rank c = DEFAULT_CAPACITY, Rank s = 0, T v = 0) {
        //容量赋值给_capacity,并new 数组
        elem = new T[capacity = c];
        for (size = 0; size < s; elem[size++] = v);
    }
    //数组整体复制
    Vector(T const *A, Rank n)
    {
        copyFrom(A, 0, n);
    }
    //使用部分数组，进行初始化
    Vector(T const *A, Rank lo, Rank hi)
    {
        copyFrom(A, lo, hi);
    }
    //向量整体复制
    Vector(Vector<T> const &V)
    {
        copyFrom(V.elem, 0, V._size);
    }
    //使用部分向量进行初始化
    Vector(Vector<T> const &V, Rank lo, Rank hi)
    {
        copyFrom(V.elem, lo, hi);
    }
    /**
     * 析构函数,释放内部空间
     */
    ~Vector()
    {
        delete[] elem;
    }
    /**
     * 只读访问接口
     */
    //返回数组的规模，c++中方法名跟变量名不能相同
    Rank getSize() const
    {
        return size;
    }
    //判空，const 修饰成员函数，此函数不应该修改任何成员变量。
    bool isEmpty() const
    {
        return !size;
    }
    //无序向量整体查找
    Rank find ( T const& e ) const
    {
        return find ( e, 0, size );
    }
    //无序向量区间查找
    Rank find ( T const& e, Rank lo, Rank hi ) const;
    //有序向量整体查找
    Rank search ( T const& e ) const
    {
        return ( 0 >= size ) ? -1 : search ( e, 0, size );
    }
    //有序向量区间查找
    Rank search ( T const& e, Rank lo, Rank hi ) const;
    /**
     * 可写访问接口
     */
    //重载下标操作符，可以类似于数组形式引用各元素
    T& operator[] ( Rank r );
    //仅限于做右值的重载版本
    const T& operator[] ( Rank r ) const;
    //重载赋值操作符，以便直接克隆向量
    Vector<T> & operator= ( Vector<T> const& );
    //删除秩为r的元素
    T remove ( Rank r );
    //删除秩在区间[lo, hi)之内的元素
    Rank remove ( Rank lo, Rank hi );
    //插入元素
    Rank insert ( Rank r, T const& e );
    //默认作为末尾元素插入
    Rank insert ( T const& e )
    {
        return insert ( size, e );
    }
    //对[lo, hi)排序
    void sort ( Rank lo, Rank hi );
    //整体排序
    void sort()
    {
        sort ( 0, size );
    }
    //对[lo, hi)置乱
    void unsort ( Rank lo, Rank hi );
    //整体置乱
    void unsort() { unsort ( 0, size ); }
    //无序去重
    Rank deduplicate();
    //有序去重
    Rank uniquify();
    /**
     * 遍历
     */
    //遍历（使用函数指针，只读或局部性修改）
    void traverse ( void (* ) ( T& ) );
    //遍历（使用函数对象，可全局性修改）
    template <typename VST> void traverse ( VST& );
};

